// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 以下代码定义了一个 Graph 结构来表示具有目标节点 to 和权重 weight 的加权边。
type Graph struct {
	to     int
	weight float64
}

// floydWarshall 函数将图形的二维切片作为输入，
// 并返回图形中所有节点对之间的最短路径距离的二维切片。
func floydWarshall(g [][]Graph) [][]float64 {

	// 创建一个 2D 切片以保存图中所有节点对之间的最短路径距离
	distance := make([][]float64, len(g))
	for i := range distance {
		dist := make([]float64, len(g))

		// 将除源节点之外的所有节点的距离设置为无穷大
		for j := range dist {
			dist[j] = math.Inf(1)
		}
		dist[i] = 0
		distance[i] = dist
	}

	// 将每个节点与其邻居之间的距离设置为其相应的边权重。
	for u, Graphs := range g {
		for _, v := range Graphs {
			distance[u][v.to] = v.weight
		}
	}

	// 如果通过第三个节点找到更短路径，则遍历所有节点对并更新它们的最短路径距离
	for k, dk := range distance {
		for _, di := range distance {
			for j, dij := range di {
				if d := di[k] + dk[j]; dij > d {
					di[j] = d
				}
			}
		}
	}

	// 返回图中所有节点对之间的最短路径距离的二维切片
	return distance
}

func main() {
	graph := [][]Graph{
		1: {{5, 9}, {2, 3}, {3, -5}},
		2: {{2, 5}, {5, 6}},
		3: {{3, 6}, {4, 8}},
		4: {{3, 7}, {1, -3}},
		5: {{1, 0}},
	}

	distance := floydWarshall(graph)
	//distance[][] 将是最终的输出矩阵
	for _, d := range distance {
		fmt.Printf("%4g\n", d)
	}
}

//$ go run floydWarshall.go
//[   0 +Inf +Inf +Inf +Inf +Inf]
//[+Inf    0    3   -5    3    9]
//[+Inf    6    5    1    9    6]
//[+Inf    5    8    0    8   14]
//[+Inf   -3    0   -8    0    6]
//[+Inf    0    3   -5    3    0]
